class Solution {
public:
    void heapify(vector<int>&arr,int i,int size){
        int l=i*2+1;//左孩子的下标
        while(l<size){
            //最强下标：有右孩子并且右孩子大于左孩子就是右孩子大，否则是左孩子大
            int best=l+1<size&&arr[l+1]>arr[l]?l+1:l;
            best=arr[best]>arr[i]?best:i;
            if(best==i)
                break;
            swap(arr[best],arr[i]);
            i=best;//更新i
            l=i*2+1;//更新left为下一轮做准备
        }
    }
    void heapsort(vector<int>&arr){
        int n=arr.size();
        for(int i=n-1;i>=0;i--){
            heapify(arr,i,n);
        }
        int size=n;
        while(size>1){
            swap(arr[0],arr[--size]);
            heapify(arr,0,size);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        heapsort(nums);
        return nums[nums.size()-k];
    }
};